import java.util.Arrays;
import java.util.NoSuchElementException;

public class MyPriorityQueue {
    //用堆模拟实现优先级队列

    //数组容器大小
    private int[] array = new int[100];
    //数组里面有效个数
    private int size = 0;

    public void createHeap(int[] array) {
        size = array.length;
        int root = ((array.length - 2) >> 1);
        // 复制数组内容
        System.arraycopy(array, 0, this.array, 0, size);
        for (; root >= 0; root--) {
            shiftDown(root);
        }
    }

    /**
     * 添加方法
     *
     * @param e 数据
     */
    public void offer(int e) {
        if (size == array.length) {
            array = Arrays.copyOf(array, array.length * 2);
        }
        array[size++] = e;
        //进行调整
        shiftUp(size - 1);
    }

    /**
     * 把元素进行移位
     * 大根堆
     *
     * @param child 移位元素的下标
     */
    public void shiftUp(int child) {
        //先找到child的双亲
        int perent = (child - 1) / 2;
        //进行循环判断
        while (child > 0) {
            //判断该孩子是否比双亲大
            if (array[perent] > array[child]) {
                break;
            } else {
                //将双亲与孩子节点进行交换
                int tmp = array[perent];
                array[perent] = array[child];
                array[child] = tmp;

                //小的元素向下移动，可能到下个子树不满足堆的性质，需要继续向上调整
                child = perent;
                perent = (child - 1) / 2;
            }
        }
    }

    /**
     * 移除队顶元素
     *
     * @return
     */
    public int poll() {
        if (size == 0) {
            throw new NoSuchElementException("Queue is empty");
        }
        //先取到队顶元素的值
        int oldValue = array[0];
        //将最后一个元素 把队顶元素的值进行覆盖 并将数组长度减一
        array[0] = array[--size];
        //对整个数组进行大根堆调整
        shiftDown(0);
        return oldValue;
    }

    public void shiftDown(int parent) {
        //child 先标记parent的左孩子，因为parent先有左孩子才能有右孩子
        int child = parent * 2 + 1;

        while (child < size) {
            //如果右孩子存在，找到左右孩子比较大的孩子，用child进行标记
            if (child + 1 < size && array[child + 1] > array[child]) {
                child++;
            }

            //如果双亲比其最大的孩子还大，说明已经满足堆的特性了
            if (array[parent] >= array[child]) {
                break;
            } else {
                //将双亲与最大的孩子进行交换
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
            }

            //继续向下调整
            parent = child;
            child = parent * 2 + 1;
        }
    }

    public int peek() {
        return array[0];
    }

    // 打印堆的内容（可选）
    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
